package com.yuhuan.data_structures;
import java.util.Random;
import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * <p>
 * Title:com.yuhuan.data_structures
 * </p>
 * <p/>
 * <p>
 * Description: 描述【】
 * </p>
 * <p/>
 * <p>
 * Copyright: Copyright (c) 2018
 * </p>
 * <p/>
 * <p>
 * School: 太原工业学院
 * </p>
 *
 * @author GuoYuhuan
 * @version 1.0
 * @created 2020/7/8 12:04
 */
public class Sort {


    public static void main(String[] args) {

        Sort s = new Sort();
        int arr[] = {2, 3, 1, 4, 6, 7, 9, 8, 5};
        int arr2[] = {4, 6, 8, 2, 1, 5, 7, 9, 3};
        int arr1[] = {1,3,45,22,877,9,8,7,6,5,4,3,2,1,12,13,10,33,21,45,0,10};
        int arr4[] = {3,6,2,1,5,4};
        int arr3[] = {6,5,4,3,2,1};



        int start = 10; int end = 100000; double[] temp1,temp2,temp3,temp4; long time1,time2,time3;
        Random random = new Random();
        double[] testArray = random.doubles(50000, start, end).toArray();
        temp1 = testArray.clone();
        temp2 = testArray.clone();
        temp3 = testArray.clone();
        temp4 = testArray.clone();


        time3 = System.currentTimeMillis();
        s.bubbleSort3(temp2);
        System.out.println("优化后的冒泡排序时间： " + (System.currentTimeMillis() - time3) + "ms");

        time2 = System.currentTimeMillis();
        s.bubbleSort1(temp1);
        System.out.println("普通冒泡排序时间： " + (System.currentTimeMillis() - time2) + "ms");


        time1 = System.currentTimeMillis();
        s.quickSort_inner(0,temp3.length-1,temp3);
//        System.out.println(Arrays.toString(temp4));
        System.out.println("快速排序时间： " + (System.currentTimeMillis() - time1) + "ms");


//        s.quickSort_inner(0,arr3.length-1,arr3);


//        System.out.println(Arrays.toString(testArray));
//        System.out.println(result);
//        System.out.println(s.insertSort1(arr));
//        System.out.println(s.insertSort2(arr));
//        System.out.println(s.bubbleSort3(arr));
//        s.test();
//        System.out.println("冒泡"+s.bubbleSort1(arr));
    }


    public String bubbleSort1(double numbers[]){

        int i,j;
        for(i=0;i<numbers.length-1;i++)
        {
            for(j=0;j<numbers.length-1-i;j++)
            {
                if(numbers[j]>numbers[j+1])
                {
                    double temp=numbers[j];
                    numbers[j]=numbers[j+1];
                    numbers[j+1]=temp;
                }
            }
        }

        return Arrays.toString(numbers);
    }

    /**
     * 冒泡排序！！！！！！！！！！！！！ zc
     * @param arr
     * @return
     */
    public String bubbleSort3(double arr[]) {
        Boolean flag = true;
        int n = arr.length;
        for (int i = 0; i < n - 1 && flag; i++) {
            flag = false;
            double temp = arr[0];
            int j;
            for (j = 1; j < n - i; j++) {
                if (arr[j] < temp) {
                    arr[j - 1] = arr[j];
                    flag = true;
                }
                if (arr[j] > temp) {
                    arr[j - 1] = temp;
                    temp = arr[j];
                }
            }
            arr[j - 1] = temp;
        }
       return Arrays.toString(arr);
    }


    /**
     * 插入排序算法1
     * @param array
     * @return
     */
    public String insertSort1(int [] array) {
        int a = 0;
        for (int i = 1; i < array.length; i++) {//待比较数据
            for (int j = 0; j < i; j++) {//被比较数据
                if (array[j] > array[i]) {//待比较数据 < 被比较数据 ，交换位置
                    a = array[i];
                    array[i] = array[j];
                    array[j] = a;
                }
            }
        }
        return Arrays.toString(array);
    }

    public void test (){
        double a,b,c,d;
        for(a=0.01;a<7.11;a+=0.01){

            for(b=0.01;b<7.11;b+=0.01){
                for(c=0.01;c<7.11;c+=0.01){

                    d=7.11-a-b-c;
                    if((a*b*c*d==7.11)&&(7.11==a*b*c*d)&&(a>0)&&(b>0)&&(c>0)&&(d>0)){
                        System.out.println("a="+a+"b="+b+"c="+c+"d="+d);
                    }
                }
            }
        }
    }

    /**
     * 插入排序算法2！！！！！！！！！！！！！！
     * @param arr
     */
    public String insertSort2(int [] arr){
        int number;
        for(int i=1;i<arr.length;i++){
            number=arr[i];
            int j=i-1;
//            这里只进行赋值，交换留到最后，一次交换=三次赋值，减少交换次数，降低时间复杂度
            while(j>=0&&arr[j]>number){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=number;
        }
        return Arrays.toString(arr);
    }

    /**
     * 快速排序 zc
     * @param m 数组第一个下标
     * @param n 数组最后一个下标
     * @param arr 需要排序的数组
     */
    public void  quickSort_inner(int m ,int n,double [] arr){
//        if (n==m|m>=arr.length-1){
//            return;
//        }
        if (m>=n){
            return;
        }
        double number;int i=m,j=n;
        number=arr[i];
        boolean flag = false; //设置flag值的意义：为了保证在一轮排序中两个if交替执行，而不会出现一边一直执行的情况
        while (i<j){//        第一遍快速排序，以arr[1]为分界线，左边小于arr[1]，右边大于arr[1]
            while (number<=arr[j]&&j>i){
                j--;
            }
            if(i!=j&&!flag&&i<arr.length-1){
                arr[i]=arr[j];
                i++;
                flag=true;
            }
            while (arr[i]<number&&i!=j&&i<arr.length-1){
                i++;
            }
            if(i!=j&&flag&&j>i){
                arr[j]=arr[i];
                j--;
                flag=false;
            }
        }
        arr[i]=number;//其实上面的两个if和if里面的赋值，简单一点可以变成一次交换，一次交换=三次赋值。
        // 而这里思想其实是比较懒的一种想法，等到一轮快速排序之后再放最终的结果，
        // 中间可以把很多不必要的一次交换变成一次赋值，提高效率。
        quickSort_inner(m,j,arr);
        quickSort_inner(j+1,n,arr);
    }
}
